import sortedcontainers
import heapq


class Solution:
    def secondGreaterElement(self, nums):
        pre_nums = nums.copy()
        n = len(nums)
        nums = [[- num, index] for index, num in enumerate(nums)]
        heapq.heapify(nums)
        ans = [-1] * n
        st = sortedcontainers.SortedList()
        now_st = []
        while nums:
            num, index = heapq.heappop(nums)
            num = - num
            if now_st and pre_nums[now_st[-1]] == num:
                now_st.append(index)
            else:
                for a in now_st:
                    insert_index = st.bisect_right(a)
                    if insert_index <= len(st) - 2:
                        ans[a] = st[insert_index + 1]
                for a in now_st:
                    st.add(a)
                now_st = []
                now_st.append(index)
        for a in now_st:
            insert_index = st.bisect_right(a)
            if insert_index <= len(st) - 2:
                ans[a] = st[insert_index + 1]
        out = []
        for index in ans:
            if index == -1:
                out.append(index)
            else:
                out.append(pre_nums[index])
        return out


data = Solution()
nums = [2, 4, 0, 9, 6]
print(data.secondGreaterElement(nums))
